package tree.huffmanTree;


import java.util.ArrayList;
import java.util.Collections;

/**
 * 霍夫曼树创建：
 * 给你一个数列{8, 11, 23, 29, 14, 7, 3, 5}，要求转为一颗霍夫曼树
 * 参考来源：https://blog.csdn.net/wuxudong12138/article/details/100032443
 */
public class HuffmanTree {
    public static void main(String[] args) {
        int[] arr = {8, 11, 23, 29, 14, 7, 3, 5};
        Node huffman = huffman(arr);
        huffman.preOrder();
        System.out.println(huffman);
    }

    private static Node huffman(int[] arr) {
        // arr中每一个元素放进了集合中
        ArrayList<Node> nodes = new ArrayList<>();
        for (int i : arr) {
            nodes.add(new Node(i));
        }
        while (nodes.size() > 1) {
            Collections.sort(nodes);
            Node left = nodes.get(0);
            Node right = nodes.get(1);
            // 新建一个根节点
            Node root = new Node(left.getWeight() + right.getWeight());
            root.setLeft(left);
            root.setRight(right);
            // 删除二个节点
            nodes.remove(left);
            nodes.remove(right);
            // 将跟节点添加进集合中
            nodes.add(root);
        }
        // 返回霍夫曼树的root节点
        return nodes.get(0);
    }


}



